1. FIELD OF THE INVENTION
The present invention relates to means for eliminating hidden surface in a three-dimensional computer graphics device for displaying a three-dimensional polyhedral object on a two-dimensional screen.
2. DESCRIPTION OF PRIOR ART
When a three-dimensional object is to be displayed on a two-dimensional screen, it is necessary to deal with a phenomenon in which a front object hides all or a portion of a rear object. In general, a scan line algorithm which serially processes by a general purpose processor and a Z-buffer algorithm which is suitable for hardware implementation have been known. In the Z-buffer algorithm, color and intensity (hereinafter simply referred to as intensity) of a plane to be displayed and a depth of the plane are stored for each pixel, and each time a new plane is inputted, the stored depth and a new plane depth are compared, and only when the new plane depth is smaller, the stored depth is updated and intensity data of the new plane is registered. When depth registers (generally called Z buffer) are provided for all pixels, a very large memory is required but a control logic is relatively simple.
On the other hand, in the scan line algorithm, the fact that when intensity data of each pixel is to be displayed for each raster scan like in a CRT, adjacent pixels and pixels on immediately adjacent scan lines have very strong correlation with the current pixel, is taken into account. It is suitable for a sequential processor but requires many operations and the control logic is complex.
As an intermediate method of those hidden line elimination algorithms, an algorithm which utilizes the correlation for cross-scan line and the Z-buffer algorithm within the line has been proposed by N. Gharachorloo et al, "Super Buffer: A Systolic VLSI Graphics Engine for Real Time Raster Image Generator", 1985 Chapel Hill Conference on Very Large Scale Integration, pp. 285-305.
FIG. 1 shows a system block diagram of the proposed means for eliminating hidden surface. Numeral 100 denotes a pixel processor, provided one for each of pixels on an N-pixel scan line. The pixel processor comprises a pixel number register which stores a location of the pixel on the scan line, a depth register which stores a depth coordinate of a plane which is present frontmost as viewed from the pixel location, an intensity register which stores intensity information of the plane, adders for updating the depth coordinate, a pixel number comparator and a depth coordinate comparator.
An operation of the means for eliminating the hidden surface thus configured is now explained with reference to a conceptual chart shown in FIG. 2.
As shown in FIGS. 2A and 2B, a plane 200 defined in a three-dimensional space (generally called normalized device coordinates) including X and Y coordinates corresponding to an M .times. N two-dimensional screen and depth information or Z coordinate, is projected onto an XY plane to display it on the screen. In a raster scan type CRT, this process is performed for each horizontal scan. The process is done on the XZ plane sectioned along a current scan line. A sectional plane sectioned along the current scan line is called a plane segment 201. Each plane segment has left end coordinates (X.sub.L, Z.sub.L), a right end X coordinate X.sub.R, a Z coordinate displacement per unit pixel dZ/dX (hereinafter designated by Z') and intensity information I. Tokens having those information are supplied to the leftmost pixel processor 100 of the array of pixel processors provided one for each pixel as shown in FIG. 1. Each pixel processor 100 first determines if its location ID on the scan line (pixel number register) meets EQU XLi .ltoreq. ID .ltoreq. XRi (1)
If it is met, the pixel processor determines if the Z coordinate Zi of the input token is smaller than data Zb stored in the depth register. If it is met, the data Zi and the intensity information Ii in the input token are stored into the depth register and the intensity register, respectively. When the relation (1) is met, the Z coordinate displacement Zi' is added irrespective of the magnitude of the Z coordinate, and other parameters are outputted as they are to the right side pixel processor.
When all plane segments on one scan line have been inputted in the form of token to the leftmost pixel processor of the array, intensity data stored in the pixel processors are read out. To this end, refresh tokens different from the plane segment tokens are inputted to the left end of the array. The refresh token has information to distinguish it from other tokens. The refresh operation is explained with reference to FIGS. 1 and 3. When the pixel processor detects the input of the refresh token R, it outputs the data Ib of the intensity register to the left side pixel processor, and in other cases, it outputs the intensity data from the right side pixel processor to the left side pixel processor. As shown in FIG. 3, the refresh token R propagates in the array and the intensity data is outputted on the left side of the array at every other cycle.
In a graphic display device which approximates a three-dimensionally defined object by a polyhedron, transforming coordinates and displaying it on a two-dimensional screen, a smooth shading method may be employed to smoothly change the intensity of displayed polygon in order to enhance a stereographic feeling.
The smooth shading method is disclosed by H. Gouraud "Continuous Shading of Curved Surfaces", IEEE Transactions on Computers, C-20 (6), June 1971, pp. 623-628.
FIG. 4 illustrates a principle of the smooth shading method. Intensities I.sub.1, I.sub.2 and I.sub.3 given to vertices of the polygon are linearly interpolated for edges, and then intensities I.sub..alpha. and I.sub..beta. at crosspoints of the edges and the raster scan line are linearly interpolated to calculate an intensity Ip of any pixel.